package 抽象数据类型;

import java.util.LinkedList;
import java.util.Queue;

public class BinTreeNode extends Node implements Comparable {
    private BinTreeNode parent; //父结点
    private BinTreeNode lChild; //左孩子
    private BinTreeNode rChild; //右孩子
    private int height; //以该结点为根的子树的高度
    private int size; //该结点子孙数（包括结点本身）

    public BinTreeNode() {
        this(null);
    }

    public BinTreeNode(Node e) {
        data = e;
        height = 0;
        size = 1;
        parent = lChild = rChild = null;
    }


    /******辅助方法,判断当前结点位置情况******/
    //判断是否有父亲
    public boolean hasParent() {
        return parent != null;
    }

    public static void levelOrder(BinTreeNode root) {
        Node temp = null;
        Queue<BinTreeNode> queue = new LinkedList<BinTreeNode>();
        if (root == null) {
            return;
        }
        queue.add(root);

        while (!queue.isEmpty()) {

            temp = queue.remove();
            System.out.println(temp.getData());
            if (((BinTreeNode) temp).getLChild() != null) {
                queue.add(((BinTreeNode) temp).getLChild());
            }
            if (((BinTreeNode) temp).getRChild() != null) {
                queue.add(((BinTreeNode) temp).getRChild());
            }

        }
    }

    //判断是否有左孩子
    public boolean hasLChild() {
        return lChild != null;
    }

    //判断是否有右孩子
    public boolean hasRChild() {
        return rChild != null;
    }

    //判断是否为叶子结点
    public boolean isLeaf() {
        return !hasLChild() && !hasRChild();
    }

    //判断是否为某结点的左孩子
    public boolean isLChild() {
        return (hasParent() && this == parent.lChild);
    }

    //判断是否为某结点的右孩子
    public boolean isRChild() {
        return (hasParent() && this == parent.rChild);
    }

    /******与 height 相关的方法******/
    //取结点的高度,即以该结点为根的树的高度
    public int getHeight() {
        return height;
    }

    //更新当前结点及其祖先的高度
    public void updateHeight() {
        int newH = 0;//新高度初始化为 0,高度等于左右子树高度加 1 中的大者
        if (hasLChild()) newH = Math.max(newH, 1 + getLChild().getHeight());
        if (hasRChild()) newH = Math.max(newH, 1 + getRChild().getHeight());
        if (newH == height) return; //高度没有发生变化则直接返回
        height = newH; //否则更新高度
        if (hasParent()) getParent().updateHeight(); //递归更新祖先的高度
    }

    /******与 size 相关的方法******/
    //取以该结点为根的树的结点数
    public int getSize() {
        return size;
    }

    //更新当前结点及其祖先的子孙数
    public void updateSize() {
        size = 1; //初始化为 1,结点本身
        if (hasLChild()) size += getLChild().getSize(); //加上左子树规模
        if (hasRChild()) size += getRChild().getSize(); //加上右子树规模
        if (hasParent()) getParent().updateSize(); //递归更新祖先的规模
    }

    /******与 parent 相关的方法******/
    //取父结点
    public BinTreeNode getParent() {
        return parent;
    }

    //断开与父亲的关系
    public void sever() {
        if (!hasParent()) return;
        if (isLChild()) parent.lChild = null;
        else parent.rChild = null;
        parent.updateHeight(); //更新父结点及其祖先高度
        parent.updateSize(); //更新父结点及其祖先规模
        parent = null;
    }

    /******与 lChild 相关的方法******/
    //取左孩子
    public BinTreeNode getLChild() {
        return lChild;
    }

    //设置当前结点的左孩子,返回原左孩子
    public BinTreeNode setLChild(BinTreeNode lc) {
        BinTreeNode oldLC = this.lChild;
        if (hasLChild()) {
            lChild.sever();
        } //断开当前左孩子与结点的关系
        if (lc != null) {
            lc.sever(); //断开 lc 与其父结点的关系
            this.lChild = lc; //确定父子关系
            lc.parent = this;
            this.updateHeight(); //更新当前结点及其祖先高度
            this.updateSize(); //更新当前结点及其祖先规模
        }
        return oldLC; //返回原左孩子
    }

    /******与 rChild 相关的方法******/
    //取右孩子
    public BinTreeNode getRChild() {
        return rChild;
    }

    //设置当前结点的右孩子,返回原右孩子
    public BinTreeNode setRChild(BinTreeNode rc) {
        BinTreeNode oldRC = this.rChild;
        if (hasRChild()) {
            rChild.sever();
        } //断开当前右孩子与结点的关系
        if (rc != null) {
            rc.sever(); //断开 lc 与其父结点的关系
            this.rChild = rc; //确定父子关系
            rc.parent = this;
            this.updateHeight(); //更新当前结点及其祖先高度
            this.updateSize(); //更新当前结点及其祖先规模
        }
        return oldRC; //返回原右孩子
    }


}
